The behavior and operation of devices may be described using abstract state machines (ASMs). For each action that the device may taken, the ASM defines conditions that must be met to effect changes to the state of the device. The conditions may be said to “guard” changes to the device state, and may thus be referred to as guards on the device state. In a normalized form, state settings, for each action that the device may take are guarded by simple (e.g. non-nested) conditions. For a more complete description of normalized ASMs, see Y. Gurevich, Evolving Algebra, 1993: Lipari Guide, and In Egon Boerger, Specification and Validation Methods, pages 9–36, Oxford University Press, 1995. ASMs have applications beyond describing the behavior and operation of devices. For example, ASMs may describe the behavior and operation of software programs executing on a general purpose computer system.
Each unique combination of state settings represents a state of the device in the ASM. For this reason, ASMs may have a large, even infinite number of states. For example, consider a simple device comprising a door that can be opened and closed. The device may include a counter which tracks the number of times the door has been closed. The counter is a state setting. An ASM for the device has an infinite number of states, one for each potential value of the counter.
Well known techniques exist for generating test suites from finite state machines (FSMs), e.g. state machines with a finite number of states. FSMs define the behavior of a device in terms of device states and the events that result in state changes.
Due to the very large or infinite number of states of the ASMs, it is often impractical to apply to ASMs the techniques for generating test suites from FSMs. A need exists for a manner of producing an FSM from an ASM, which would lead to the application of FSM test suite generation techniques to ASMs.